// 滑动窗口 - 经典找最长/短 字串/子数组 问题，都可以使用滑动窗口
// 利用 单调性， 使用 同向双指针 的方法进行优化，使得时间复杂度降低 O(N)
// 定义 双指针 用于维护 窗口 的左右边界
// 进窗口 -> 判断是否出窗口，过程中统计结果

// 例题 6：
// 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
//
//        示例 1:
//
//        输入: s = "cbaebabacd", p = "abc"
//        输出: [0,6]
//        解释:
//        起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//        起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
//        示例 2:
//
//        输入: s = "abab", p = "ab"
//        输出: [0,1,2]
//        解释:
//        起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
//        起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
//        起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
//
//
//        提示:
//
//        1 <= s.length, p.length <= 3 * 104
//        s 和 p 仅包含小写字母

// 解题思路：
// 可以使用哈希表维护字符和数量，也可以使用一个数组维护字符和数量，以及再定义一个变量count维护有效字符的个数
// 与例题 1 相同
// 进窗口：统计字符及数量 判断是否为有效字符
// 如果字符数量大于 p 字符的数量 ，出窗口，判断是否为有效字符
// 如果有效字符的数量等于 p 字符的数量，更新结果

import java.util.ArrayList;
import java.util.List;

public class FindAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int m = s.length();
        int n = p.length();
        char[] sArr = s.toCharArray();
        char[] pArr = p.toCharArray();
        // 使用两个哈希表统计 s 和 p 中的字符及数量
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        // 使用一个 count 来统计哈希表 1 中有效字符的个数
        int count = 0;
        for(int i = 0; i < n; i++) hash2[pArr[i] - 'a']++;

        int left = 0; int right = 0;
        while(right < m){
            hash1[sArr[right] - 'a']++;
            if(hash1[sArr[right] - 'a'] <= hash2[sArr[right] - 'a']) count++;
            while(right - left + 1 > n) {
                hash1[sArr[left] - 'a']--;
                if(hash1[sArr[left] - 'a'] < hash2[sArr[left] - 'a']) count--;
                left++;
            }
            if(right - left + 1 == n && count == n) ret.add(left);
            right++;
        }
        return ret;
    }
}
